Communications networks are known in the art. An ad-hoc network is a network formed by wireless hosts without a pre-existing infra-structure. The participants in the network, known as nodes, communicate between each other directly or via other nodes (i.e., a node may perform the operation of a router). Nodes in ad-hoc networks, may arrange themselves in clusters of nodes. The nodes in each cluster select a cluster-head from the nodes in the cluster. The cluster head may be operative to route message between the nodes in the cluster and the nodes in other clusters. Nodes may leave or join the cluster. Therefore, the number of nodes in a cluster may vary. The node designated as the cluster-head may change. For example, the current cluster-head of the cluster leaves the cluster or the network. A new cluster-head will be selected from the remaining nodes in the cluster.
Reference is now made to FIG. 1, which is a schematic illustration of a simple exemplary wireless ad-hoc network, generally referenced 10, which is known in the art. Network 10 includes nodes 12, 14, 16, 18, 20, 22, 24, 26. Nodes 12, 14, 16 and 18 form a cluster, and node 12 is designated as a cluster head and router. Nodes 20, 22, 24 and 26 form another cluster, and node 20 is designated as a cluster-head and router. The dashed line, connecting the nodes, indicates that the nodes communicate with each other, but are not physically connected.
For example, node 16 desires to communicate information to node 26. Node 16 will communicate the information to router 12, router 12 will communicate the information to router 20 and router 20 will communicate the information to node 26. The path or route from node 16 to 26 traverses through routers 12 and 20. In another example, node 14 wishes to communicate information to node 18. Since these two nodes belong to the same cluster therefore node 14 will transmit directly to node 18.
US patent application publication 2002/0112286 A1 to Iwamura et al, entitled “Network Construction Method and Communication System for Communicating Between different Groups Via Representative Devices Of Each Group” directs to establishing a communication network consisting of nodes, arranged in clusters. Associated with each cluster is a cluster-heads. Initially, each node broadcasts a message containing information about itself (e.g., an identification number) and other nodes from which the broadcasting node received a message. Consequently, each node knows about other nodes, from which it can receive a message. The technique divides the network to clusters of several nodes. The nodes in each cluster can communicate with each other. A cluster-head is selected from among the nodes in the cluster. The cluster-head communicates with cluster-heads of other clusters. Consequently, a node, belonging to one cluster, may send a message to a node in another cluster. The receiving node may send a message to the transmitting node, acknowledging the reception of the message. The information about routes to different nodes is stored in each node.
Iwamura et al, further direct to a technique in which a cluster-head identifies a new node joining the network, and identifies a route to that node when the new node is not in the cluster of the cluster-head. The technique further provides means to detect if a message reached the destination, the message is destined thereto. Iwamura et al, further direct to a technique in which nodes may detect nodes of other clusters in the surroundings of the node.
U.S. Pat. No. 6,744,740 to Chen entitled “Network Protocol for Wireless Devices Utilizing Location Information” directs to a technique in which nodes, in an ad-hoc network, are arranged in clusters with designated cluster-heads. A cluster-head is cognizant of the position of the nodes in the own cluster of the cluster-head. A designated node, not necessarily the cluster-head, functions as a gateway between different clusters. The gateway relays messages between cluster-heads. The information may include the position of the cluster-head and the positions of the nodes in the cluster. Cluster-heads periodically exchange information about other clusters. Therefore, all the cluster-heads in the network are informed of all the other clusters.
A node, required to send a message to another node, creates a list of all the nodes within a number of hops away. If the other node is in the list, then the node will forward the message to the other node. The node forwards the message directly or via an intermediate node. If the node forwards the message via intermediate nodes, then, the node selects the node with the shortest distance to the destination as the next node. If the other node is not in the list, then the node will send a query to cluster-head of the node thereof. The cluster-head will query other cluster-heads in the network. Thus, a route to the destination node is discovered.
Reference is now made to a publication to N. K. Guba and T. Camp, entitled “GLS: a Location Service for an Ad Hoc Network”, in Proceedings of the Grace Hopper Celebration (GHC '02), 2002. This publication is directed to an ad hoc network, wherein each node, maintains the geographical position thereof, using a GPS. Each node utilizes Grid Location Service (i.e., GLS) to forward messages to other nodes in the network. In this GLS, the network coverage area is initially arranged into a hierarchy of grids with squares of increasing size. The smallest square is called an order-1 square. Four order-1 squares form an order-2 squares etc. Each node selects a location server in each of its neighboring squares of any order. When a node needs a location for a destination, it initiates a location query request to a potential location server of the destination node, in the requesting node order-2 square. The receiving node sends the query to the servers of a neighboring higher order squares using the same method. The process is repeated until the query reaches the GLS selected by the destination node. The receiving GLS sends the message to the destination node. The destination node responds to the query by sending its most recent location using this same method. When a node moves it sends a location update to all of its location servers. When a node moves to a different square it leaves, in its old square, a pointer to the new square of the node.
U.S. Pat. No. 5,652,751 to Sharony entitled “Architecture for Mobile Radio Networks with Dynamically Changing Topology Using Virtual Subnets” Directs to a radio network, having nodes that are subject to dynamically changing topology, wherein, the nodes are grouped into physical subnets and virtual subnets. A physical subnet is a group of nodes, in relatively close proximity to one another, in a defined local geographical area. A virtual subnet is a subnet affiliating each node in a physical subnet, with a corresponding node in each of the other physical subnets. The network identification representation (e.g., ID number) is composed of the physical subnet number and the next greatest possible address within the physical subnet. Each node in the network is updated with the current addresses, used in its physical and virtual subnets, by advertising processes using a dedicated management channel. Routing a message from a source node to a destination node is achieved by first sending the message to an intermediate node, affiliated with the destination node (i.e., in the same virtual subnet of the destination node), within the physical network of the source node. The intermediate node sends the message to the destination node over the virtual subnet.
U.S. Pat. No. 6,807,165, to Belcea entitled “Time Division Protocol for an Ad-Hoc, Peer-to-Peer Radio Network Having Coordinating Channel Access to Shared Parallel Data Channels with Separate Reservation Channel” directs to an ad-hoc network, wherein, each node has full information about all activities of other nodes. The nodes access the channel according to a combination of Time Division Multiple Access (i.e., TDMA), Frequency Division Multiple Access (i.e., FDMA) and Code Division Multiple Access (i.e., CDMA). A configuration channel, for transmitting configuration data (e.g., connectivity and data transfer plans), is reserved at a certain frequency. Nodes access the configuration channel according to a TDMA scheme. Using received messages, a node creates a utilization map and computes the required transmit power. Initially, the node transmits a message in the last time slot of a time frame. The message includes the utilization map of the node and a request to register with the closest node to the transmitting node. In the utilization map, the node marks the time slot it intends to move to in the next frame. A node transmits a message to another node over a route that will result in expending the least amount of energy. The route is determined according to a tree stored in each node.
U.S. Pat. No. 6,816,460 to Ahmed et al. entitled “Location Based Routing for Mobile Ad-Hoc Networks” directs to an ad-hoc network wherein each node transmits a periodic pilot signal. This pilot signal includes the location information of the transmitting node. Using the location information received from other nodes, a node constructs a point-to-point links to other nodes within a hearing distance from the node. In one embodiment of the publication to Ahmed et al, each node knows the location-(accurate or approximate) of every other node in the network. Each node periodically transmits this information to its direct neighbors. The neighbors transmit the information to their neighbors. When a node is required to transmit a message to a node with which it does not have a point-to-point link, the node transmits to an intermediate node closest to the destination node. That node sends the message either to the destination node or to another intermediate node closer to the destination node.
Reference is now made to the article by G. Pei, M. Gerla and X. Hong, entitled “LANMAR: Landmark Routing for Large Scale Wireless Ah Hoc Networks With Group Mobility” in Proceedings of IEEE/ACM Workshop on Mobile Ad Hoc Networking & Computing (MobiHoc 2000), pp 11-18, August 2000. This article directs to a technique wherein nodes forming a logical group of nodes (e.g., a brigade, soldiers in a battle field) select a landmark node representing the logical group of nodes. Thus, each node in the network is associated with a landmark. Each node in the network exchange routing information with the nodes in the local area of the node known as the fisheye scope. For example, the fisheye scope of a node may be all the one-hop and two-hop neighbors of the node. The routing information includes routes to the nodes in the local area of the node and routes to the different landmarks in the network. A node sends a message to another node in the fisheye scope of the node according to the routing table stored in the node. A node sends a message to another node, not in the fisheye scope of the node by first directing the message to the landmark of the other node. When the message reaches an intermediate node, and the destination node is within the fisheye scope of the intermediate node, the intermediate node forwards the message directly to the destination node, according to the routing table stored in the intermediate node.